
<!DOCTYPE html>
<html>

	<head>
	<title>CAIJL's Blog</title>
	<meta charset="utf-8"/>
	<link rel="stylesheet" href="/font-awesome-4.7.0/css/font-awesome.min.css">

	<link rel="stylesheet" href="/bootstrap-3.3.7/css/bootstrap.min.css">
	<script src="/jquery-2.1.1/jquery.min.js"></script>
	<script src="/bootstrap-3.3.7/js/bootstrap.min.js"></script>

	<link rel="stylesheet" href="/css/bootstrap-slider.min.css">
	<script src="/js/bootstrap-slider.min.js"></script>
	
	<link rel="stylesheet" href="/css/main.css">
	<script src="/js/main.js"></script>
	
	<link rel="stylesheet" href="/css/cursor.css">
	<script src="/js/cursor.js"></script>
	
	
	<link rel="stylesheet" href="/css/code.css">
	<!--link rel="stylesheet" href="/css/markdown.css"-->
	
	<link rel="stylesheet" href="/css/head.css">

	<script src="/js/window.js"></script>
	<script src='//unpkg.com/valine/dist/Valine.min.js'></script>
	</head>
<body>

	<link rel="stylesheet" href="/katex/katex.min.css" crossorigin="anonymous">
	<script src="/katex/katex.min.js" crossorigin="anonymous"></script>
	<script src="/katex/contrib/mathtex-script-type.min.js" defer></script>
	<script defer src="/katex/contrib/auto-render.min.js"crossorigin="anonymous"
	    onload="renderMathInElement(document.body);"></script>
	<script>document.addEventListener("DOMContentLoaded", function() {renderMathInElement(document.body,{"delimiters":[{left: "$", right: "$", display: false}]});});</script>
	<nav class="navbar navbar-default header card" role="navigation" style="width: 100%;">
	<div class="container-fluid"> 
	<div class="navbar-header">
		<button type="button" class="navbar-toggle" data-toggle="collapse"
				data-target="#example-navbar-collapse">
			<span class="icon-bar"></span>
			<span class="icon-bar"></span>
			<span class="icon-bar"></span>
		</button>
		<a class="navbar-brand" href="/"><span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="bold">C</mi><mi mathvariant="bold">A</mi><mi mathvariant="bold">I</mi><mi mathvariant="bold">J</mi><msup><mi mathvariant="bold">L</mi><mo mathvariant="bold" lspace="0em" rspace="0em">′</mo></msup><mi mathvariant="bold">s</mi><mi mathvariant="bold">B</mi><mi mathvariant="bold">L</mi><mi mathvariant="bold">O</mi><mi mathvariant="bold">G</mi></mrow><annotation encoding="application/x-tex">\mathbf{CAIJL'sBLOG}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height: 0.751892em; vertical-align: 0em;"></span><span class="mord"><span class="mord mathbf">C</span><span class="mord mathbf">A</span><span class="mord mathbf">I</span><span class="mord mathbf">J</span><span class="mord"><span class="mord mathbf">L</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height: 0.751892em;"><span class="" style="top: -3.063em; margin-right: 0.05em;"><span class="pstrut" style="height: 2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathbf mtight">′</span></span></span></span></span></span></span></span></span><span class="mord mathbf">s</span><span class="mord mathbf">B</span><span class="mord mathbf">L</span><span class="mord mathbf">O</span><span class="mord mathbf">G</span></span></span></span></span></span></a>
	</div>
	<div class="collapse navbar-collapse" id="example-navbar-collapse">
		<ul class="nav navbar-nav" style="background-color:#fcfcfc">
			<li><a href="/"><i class="menu-item-icon fa fa-fw fa-home"></i>首页</a></li>
			<li><a href="/archives/"><i class="menu-item-icon fa fa-fw fa-archive"></i>文章</a></li>
			<li><a href="/tags/"><i class="menu-item-icon fa fa-fw fa-tags"></i>标签</a></li>
			<li><a href="/settings/"><i class="menu-item-icon fa fa-fw fa-cogs"></i>设置</a></li>
			<!--li><a href="/about/"><i class="menu-item-icon fa fa-fw fa-user"></i>关于</a></li-->
			<li><a href="/games/"><i class="menu-item-icon fa fa-fw fa-gamepad"></i>其它</a></li>
			

		</ul>
	</div>
	</div>
	</nav>
<div class="container">
	<div style="height: 60px;"></div>
	<div class="row" >
		<div class="col-md-8">
			<div class="panel panel-default card" style="padding: 10px;position: relative;">
                <img src='/img/bg/39.png' style="width:100%"/>
				<span style="position: absolute;left:15px;bottom:15px;width:90%;"><font class="view-text" style="color:#fcfcfc;font-size:25px">省选联考 2020 口胡记录</font><br><a href="/tags/2021/" class="tag"><span  style="background-color: rgb(52, 152, 219);">2021</span></a></span>
			</div>
			<div class="panel panel-default card" style="padding: 10px;" id="main">
                <h2 id="colorredhugetext">
<script type="math/tex; mode=display">\color{red}\Huge{\text{!不要看题解!}}</script>
</h2>
<h2 id="colorpurpletextp6623-2020-a"><a href="https://www.luogu.com.cn/problem/P6623"><script type="math/tex">\color{purple}\text{P6623 [省选联考 2020 A 卷] 树}</script></a></h2>
<p>在一棵 <script type="math/tex">\rm 01tire</script> 上怎么全局加啊...</p>
<p>因为一个数加一从后面往前影响，全局加一复杂度不大对，感觉这个 <script type="math/tex">\rm tire</script> 复杂度贼假，可能还没有暴力快。</p>
<p>看起来蒟蒻只能爆零 <img alt="" src="https://cdn.luogu.com.cn/upload/pic/62226.png"></p>
<p><del>太难了太难了弃赛罢</del></p>
<p>那么如果倒着建 <script type="math/tex">\rm tire</script> 复杂度会不会好一点？那么进位的情况似乎会简单一点。</p>
<p>维护一下每一位 <script type="math/tex">0</script> 和 <script type="math/tex">1</script> 的个数，每次启发式合并一下就好了。</p>
<p>
<script type="math/tex">\sf\color{red}\text{总结}</script>：<script type="math/tex">\rm tire</script> 不一定要从高位往低位，惯性思维害人不浅<img alt="wq" src="https://cdn.luogu.com.cn/upload/pic/62248.png"></p>
<h2 id="colorpurpletextp6624-2020-a"><a href="https://www.luogu.com.cn/problem/P6624"><script type="math/tex">\color{purple}\text{P6624 [省选联考 2020 A 卷] 作业题}</script></a></h2>
<p>套路题，先把 <script type="math/tex">\gcd</script> 反演掉，然后直接矩阵树即可。边权为 <script type="math/tex">1+w_ix</script> 乘起来提取 <script type="math/tex">x^1</script> 即为 <script type="math/tex">\sum w_i</script> 了。</p>
<h2 id="colorblacktextp6621-2020-a"><a href="https://www.luogu.com.cn/problem/P6621"><script type="math/tex">\color{black}\text{P6621 [省选联考 2020 A 卷] 魔法商店}</script></a></h2>
<p>论文题不会。</p>
<h2 id="colorpurpletextp6620-2020-a"><a href="https://www.luogu.com.cn/problem/P6620"><script type="math/tex">\color{purple}\text{P6620 [省选联考 2020 A 卷] 组合数问题}</script></a></h2>
<p>直接暴力推柿子：
<script type="math/tex; mode=display">
\begin{aligned}
&\sum_{k=0}^{n}f(k)\times x^k\times \binom{n}{k}\\
=&\sum_{k=0}^n\sum_{i=0}^ma_ik^i\times x^k\times\binom nk\\
\end{aligned}
</script>
由于 <script type="math/tex">n</script> 很大，我们希望后面一坨有封闭形式。组合数引导我们使用二项式定理，可是这 <script type="math/tex">k^i</script> 不是什么好东西，让我们写不出封闭形式。</p>
<p>但是我们发现，组合数是可以吸收和释放的，换句话说：
<script type="math/tex; mode=display">\binom nk=\frac{n}{k}\binom{n-1}{k-1}=\frac{n(n-1)}{k(k-1)}\binom{n-2}{k-2}=\ldots=\frac{n^{\underline{i}}}{k^{\underline{i}}}\binom{n-i}{k-i}</script>
</p>
<p>现在已经出现 <script type="math/tex">k</script> 的 <script type="math/tex">i</script> 次了，但是是下降幂。</p>
<p>考虑将 <script type="math/tex">f</script> 化为下降幂多项式。
<script type="math/tex; mode=display">\begin{aligned}
=&\sum_{k=0}^n\sum_{i=0}^mb_ik^{\underline{i}}x^k\frac{n^{\underline{i}}}{k^{\underline{i}}}\binom{n-i}{k-i}\\
=&\sum_{i=0}^mb_in^{\underline{i}}\sum_{k=0}^nx^k\binom{n-i}{k-i}\\
=&\sum_{i=0}^mb_in^{\underline{i}}x^i\sum_{k=0}^{n-i}x^{k}\binom{n-i}{k}\\
=&\sum_{k=0}^mb_in^{\underline{i}}x^i\left(x+1\right)^{n-i}
\end{aligned}</script>
现在的问题就是普通多项式转下降幂多项式了。</p>
<p>
<script type="math/tex; mode=display">\begin{aligned}x^{\underline{i}}=\sum_{j=0}^i\left[\begin{matrix}i\\j\end{matrix}\right]x^i\\a_n=\sum_{i=n}^mb_i\left[\begin{matrix}i\\j\end{matrix}\right]\end{aligned}</script>
现在应该是可以按位递推了。</p>
<p>好像用第二类更方便一些...</p>
<h2 id="colororangetextp6625-2020-b"><a href="https://www.luogu.com.cn/problem/P6625"><script type="math/tex">\color{orange}\text{P6625 [省选联考 2020 B 卷] 卡牌游戏}</script></a></h2>
<p>前缀和为正加入答案。</p>
<h2 id="colorgreentextp6627-2020-b"><a href="https://www.luogu.com.cn/problem/P6627"><script type="math/tex">\color{green}\text{P6627 [省选联考 2020 B 卷] 幸运数字}</script></a></h2>
<p>
<script type="math/tex">n</script> 个条件把数轴划分成了 <script type="math/tex">\mathcal O(n)</script> 个区域，扫描线一下就好了。</p>
<p>
<script type="math/tex">\sf\color{red}\text{注意}</script>：扫描线的时候要加上 <script type="math/tex">0</script>
</p>
<h2 id="colorpurpletextp6619-2020-ab"><a href="https://www.luogu.com.cn/problem/P6619"><script type="math/tex">\color{purple}\text{P6619 [省选联考 2020 A/B 卷] 冰火战士}</script></a></h2>
<p>不难发现是单峰的，二分两只 <script type="math/tex">\log</script> 过不去。。。</p>
<p>先离散。</p>
<p>好像可以在线段树上二分，找到最后一个 冰 <script type="math/tex">\le</script> 火的位置 <script type="math/tex">a</script> ，最大值只能在 <script type="math/tex">a</script> 与 <script type="math/tex">a+1</script>。</p>
<p>找到最大值后再二分一下找到温度。</p>
<p>
<script type="math/tex">\sf\color{red}\text{注意}</script>：这个屑离散化写挂了大家快来 <script type="math/tex">\rm D</script> 爆他</p>
<h2 id="colorpurpletextp6622-2020-ab"><a href="https://www.luogu.com.cn/problem/P6622"><script type="math/tex">\color{purple}\text{P6622 [省选联考 2020 A/B 卷] 信号传递}</script></a></h2>
<p>
<script type="math/tex">m</script> 这么小应该是要 <script type="math/tex">\mathcal O(2^m)</script> 的。</p>
<p>想了一个晚自修只会 <script type="math/tex">\mathcal O(m!\times m^2)</script> 看来要退役了。</p>
<p>不知道怎么出现 <script type="math/tex">2^m</script> 次，应该是要状压。</p>
<p>看题解去了<img alt="youl" src="https://cdn.luogu.com.cn/upload/pic/69020.png"></p>
<p>好吧如果记 <script type="math/tex">f_S</script> 为用 <script type="math/tex">S</script> 填上 <script type="math/tex">1\sim |S|</script> 的最小值就可以 <script type="math/tex">\rm dp</script> 了，直接是 <script type="math/tex">\mathcal O(2^mm^2)</script> 了。</p>
<p><del>由于是口胡不需要细节。</del></p>
<p>
<script type="math/tex; mode=display">
x\to y\quad \begin{cases}
p_y-p_x&,&p_y> p_x\\
kp_x+kp_y&,&p_y< p_x
\end{cases}
</script>
考虑在 <script type="math/tex">S</script> 里加入一个数 <script type="math/tex">i</script>，即在 <script type="math/tex">|S|+1</script> 的位置上放 <script type="math/tex">i</script>
</p>
<p>
<script type="math/tex; mode=display">f_{S\cup \{i\}}\leftarrow f_S+(|S|+1)\sum_{j\in S}(\color{red}k\times c_{i,j}\color{b}+\color{blue}c_{j,i}\color{b})+(|S|+1)\sum_{j\not\in S\cup\{i\}}(\color{blue}-c_{i,j}\color{b}+\color{red}k\times c_{j,i}\color{b})</script>
</p>
<p>红色部分是后面到前面的贡献，蓝色部分是前面到后面的贡献。</p>
<p>记 
<script type="math/tex; mode=display">g_{S,i}=\sum_{j\in S}(k\times c_{i,j}+c_{j,i})+\sum_{j\not\in S\cup\{i\}}(-c_{i,j}+k\times c_{j,i})</script>
这个东西应该是可以递推的。</p>
<h2 id="colorpurpletextp6628-2020-b"><a href="https://www.luogu.com.cn/problem/P6628"><script type="math/tex">\color{purple}\text{P6628 [省选联考 2020 B 卷] 丁香之路}</script></a></h2>
<p>《只会 <script type="math/tex">\mathcal O(nm)</script>》</p>
<p>被 <script type="math/tex">\rm Z\color{red}LC\_AK</script> 嘲讽了<img alt="wq" src="https://cdn.luogu.com.cn/upload/pic/62248.png">。。。</p>
<p>用欧拉回路乱搞即可</p>
			</div>
			<div class="panel panel-default card" style="padding: 10px;height: 50px;font-size: 20px;">
				<a style="float: left;" href="\article\P7468.html"><i class="fa fa-angle-double-left"></i></a><a style="float: right;" href="\article\CF891E.html"><i class="fa fa-angle-double-right"></i></a>
			</div>
			<div class="panel panel-default card" style="padding: 10px;font-size: 20px;" id="vcomments">
				
			</div>
			<script>
				new Valine({
					el: '#vcomments',
					appId: 'PAlFUPg0pQVTFTEo8gCB4BCf-gzGzoHsz',
					appKey: 'U38ejnLUiizJ6vLyp6ql4hRq',
					path: window.location.pathname
				})
			</script>
		</div>
		<div class="col-md-3">
				<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-info"></i>&emsp;
						<strong>文章信息</strong>
					</h3>
				</div>
                <div style="margin: 10px;">
                    <div style="margin-top: 8px;display: flex;"> 
    <span style="flex: 1 0 auto;margin-right: 6px;">标题</span>
    <span><font style="font-weight: bold">省选联考 2020 口胡记录</font></span>
	</div><div style="margin-top: 8px;display: flex;"> 
    <span style="flex: 1 0 auto;margin-right: 6px;">日期</span>
    <span>2021-04-03 21:52:06</span>
	</div>
                </div>
				</div>
				<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-tag"></i>&emsp;
						<strong>标签</strong>
					</h3>
				</div>
				<div style="margin: 10px;">
					<a href="/tags/2021/" class="tag"><span  style="background-color: rgb(52, 152, 219);">2021</span></a>
				</div>
				</div>
				
			<div class="panel panel-default card">
					<div class="panel-heading">
						<h3 class="panel-title">
							<i class="fa fa-user-circle-o"></i>&emsp;
							<strong>caijicjl</strong>
						</h3>
					</div>
					<div style="width: 60%;display: inline-block;padding-top: 10px;">
						<ul class="propertyLinks" style="list-style-type: none;">
							<li>
								<img style="vertical-align:middle;position:relative;top:-2px" src="/img/rating-16x16.png">
								Rating:&nbsp;
								<span style="font-weight:bold;color: gray ">312</span>
							</li>
							<li>
								<img style="vertical-align:middle;position:relative;top:-2px" src="/img/star_blue_16.png">
								Contribution:&nbsp;
								<span style="color:gray;font-weight:bold;">0</span>
							</li>
						</ul>
						<ul class="nav-links">
							<li><a href="/settings/">Settings</a></li>
							<li><a href="/archives/">Blog</a></li>
							<li><a href="/teams">Teams</a></li>
							<li><a href="/submissions/dingdingsb">Submissions</a></li>
							<li><a href="/usertalk">Talks</a></li>
							<li><a href="/contests/with/dingdingsb">Contests</a></li>
						</ul>
					</div>
					<div style="display:inline-block;vertical-align: top;margin: 10px;text-align: center;">
						<div style="height:50px;width:50px"><img src="/img/avatar.png"/></div>
						<div><a href="https://www.luogu.com.cn/user/174304" style="font-weight:bold;color:gray">caijicjl</a></div>
					</div>
				</div>
		<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-external-link"></i>&emsp;
						<strong>画中画</strong>
					</h3>
				</div>
				<div style="width:100%;margin:10px">
				<input type="text" id="url"/>
				<input value="创建" type="button" onclick="creat('kk')" /> 
				</div>
		</div>
		<script src="/js/hitokoto.js"></script>
							

				
				<span id="kk"></span>
				<div  id="myScrollspy" class="card" style="width: 100%;"  data-spy="affix">
					<script src="/js/make_toc.js"></script>
				</div>
		</div>
	</div>
 </div>
</body>
</html>
